package chapter04;

import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

class Bintree implements Comparable<Bintree>{
   Bintree left=null;
   Bintree right=null;
   float weigth=0;
   char ch;
   public Bintree(char ch, float weigth) {
       
        this.ch=ch;
        this.weigth=weigth;
       }
   public Bintree(Bintree t1,Bintree t2) {
       this.left=t1;
       this.right=t2;
       this.weigth=t1.weigth+t2.weigth;

       
}
   public int compareTo(Bintree o) {
       if(this.weigth>o.weigth)
           return 1;
       else if (this.weigth<o.weigth) {
           return -1;    
    }return 0;
    
   }
   
}
public class hafuman {
    public static Map<Character, String>codes=new TreeMap<Character,String>();
    public static StringBuffer code=new StringBuffer();
    public static Bintree huffmanBintree(char[] c,float[] w) {
        PriorityQueue<Bintree>pq=new PriorityQueue<Bintree>();
        for (int i = 0; i < c.length; i++) {
            pq.add(new Bintree(c[i], w[i]));  
        }
        
        while(pq.size()>1) {
            Bintree t1=pq.poll();
            Bintree t2=pq.poll();
            pq.add(new Bintree(t1, t2));
            
            
        }
        return pq.poll();  
    }
    public static  void coding(Bintree t) {
        if(t!=null) {
            if(t.left == null && t.right ==null ) {
                codes.put(t.ch, code.toString());
                
            }
            code.append(0);
            coding(t.left);
            code.deleteCharAt(code.length()-1);
            
            code.append(1);
            coding(t.right);
            code.deleteCharAt(code.length()-1);
            
            
        }
        
    }
    public static void main(String[] args) {
        char[] c= {'a','b','c','d','e','f','g','h'};
        float[] w= {5,29,7,8,14,23,3,11};
        Bintree t=huffmanBintree(c, w);
        coding(t);
        for(char ch: c) {
            System.out.println(ch+ ":"+codes.get(ch));
        }
    }

}
